\section{Алгоритм имитации отжига}

\subsection{Аналогия с физическим процессом}
Идея алгоритма основана на имитации физического процесса, который происходит при кристаллизации вещества из жидкого состояния в 
твердое. Предполагается, что атомы уже выстроились в кристаллическую решетку, но переход атомов из одного состояние в другое
все еще возможен.
Процесс происходит при постепенно понижающейся температуре. Чем выше температура, тем более высока вероятность атома перейти из одного 
состояния в другое. Устойчивая кристаллическая решетка соответствует минимуму энергии атомов. 

\subsection{Описание алгоритма}
Пусть дана целевая функция $F(\overline{X})$, $\overline{X} = (x_1, x_2, \ldots, x_n)$. Нужно найти точку, на которой $F(\overline{X})$
достигает своего минимума. Пусть есть начальное допустимое решение $\overline{X}_0$, которое мы объявим текущим, и параметр $T$, 
который будет выполнять роль \flqqтемпературы\frqq.
Алгоритм имитации отжига заключается в следующем:

\begin{enumerate}
\item Путем небольшого изменения текущего решения $\overline{X}_n$ (по аналогии с передвижением атомов в 
кристаллической решетке), мы получаем новое решение $\overline{X}^*$. 
\item Новое решение становится текущим с вероятностью $P(\overline{X}_n, \overline{X}^*)$, которая вычисляется по следующей формуле:
	
\begin{equation}
\label{metropolisrule}
		P(\overline{X}_n, \overline{X}^*) = \left\{ \begin{array}{ll}
										    1 & \textrm{, если $F(\overline{X}^*)<F(\overline{X}_n)$} \\
											e^{\textstyle\frac{F(\overline{X}_n)-F(\overline{X}^*)}{T}} & \textrm{, иначе}
											       \end{array} 
										    \right.
\end{equation}
\item При достижении достаточного количества итераций, уменьшается параметр $T$.
\item Переход на шаг 1.
\end{enumerate}
Хотя и описание алгоритма дано, остаются неясными многие важные вещи: 
\begin{description}
 \item[Начальное значение $T$.] Очевидно, что оно зависит от начального решения. Если начальное 
	решение достаточно хорошо, то тем меньше должна быть вероятность принять решение c худшим значением целевой функции.
	Следовательно, и параметр $T$ также должен быть меньше. Есть несколько подходов для вычисления начальной температуры,
	но в той или иной степени они все похожи друг на друга, в своей работе я пользовался следующей формулой:
	\begin{displaymath}
		T_0 = \frac{\mu}{-\ln{\phi}}F(\overline{X_0}),
	\end{displaymath}
	где подразумевается, что будут приняты $\phi\%$ плохих решений, отличающихся от  $F(\overline{X}_0)$ не более чем на $\mu\%$.
 \item[Каким должно быть \flqqдостаточное количество итераций\frqq?] Этот параметр зависит от числа степеней свободы задачи. 
	Рекомендуемым значением для этого параметра является $cn$, где $c>1$ - некоторая константа, а $n$ - число степеней свободы.
 \item[Закон изменения $T$.] Здесь стоит заметить, что изменение температуры не должно быть резким.
 В литературе можно встретить множество законов изменения $T$, от самых простых до достаточно сложных,
 но на практике все они работают не лучше убывающей геометрической прогрессии. То есть:
	\begin{displaymath}
		T_{n+1} = cT_n,  \textrm{где $c<1$}
	\end{displaymath}
 \item[Условие остановки алгоритма], т.е. в какой момент можно сказать, что последовательность решений стабилизировалась, и обнаружение лучшего решения
  маловероятно. Тут есть достаточно единогласное мнение, что алгоритм должен заканчивать свою работу тогда, когда при $N$ понижениях 
  температуры, текущее решение не изменилось.
\end{description}

\subsection{Распараллеливание}
Часто время выполнения алгоритма становится критическим фактором для практических приложений. Чтобы уменьшить это время, стоит
задуматься о распараллеливании алгоритма, т.е. о параллельном вычислении нескольких стадий его реализации. Проблема 
алгоритма имитации отжига состоит в том, что он имеет последовательную структуру. Каждое новое решение зависит от предыдущего, и именно
это дает ему теоретическую основу в виде цепей Маркова, и именно это обеспечивает сходимость с вероятностью 1. Любое распараллеливание 
нарушит это правило. Тем не менее существует метод, который ведет себя достаточно хорошо и теоретически эквивалентен последовательному 
алгоритму.
Алгоритм состоит из двух стадий:
\begin{itemize}
	\item[-] Стадия, выполняющаяся на высоких температурах. Когда температура высока, число принимаемых решений также высоко.
	Поэтому стратегия состоит в следующем: каждый из $S$ процессоров выполняет $N/S$ изменений решения, а затем случайно выбирается
	процессор, чье конечное решение будет принято за новое.
	\item[-] Стадия, выполняющаяся на низких температурах. Здесь количество принимаемых решений становится мало, и следовательно 
	все они становятся важны. Поэтому каждый из $S$ процессоров выполняет $N/S$ изменений решения, пока не примет одно из них. Далее 
	процессоры тут же синхронизируются и продолжают работу.
\end{itemize}


	
